
public class LinkSort_hjl {

    public static void main(String[] args) {
        int[] data = new int[]{
                3, 5, 1, 7, 4, 6
        };

        ListNode listNode = buildLink(data);
        ListNode sortedNode = sortList(listNode);
        printLink(sortedNode);
    }

    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            //递归结束
            return head;
        }
        /*将链表分成两截*/
        ListNode midNode = findMiddleNode(head);
        ListNode leftNode = head;
        ListNode rightNode = midNode.next;
        midNode.next = null;
        /*可以将两截看成类似小规模的排序，并分别进行排序*/
        ListNode sortedLeftNode = sortList(leftNode);
        ListNode sortedRightNode = sortList(rightNode);
        /*对左右两截进行合并*/
        return mergeSortList(sortedLeftNode, sortedRightNode);
    }

    /**
     * 合并，将小的排在左边，大的排在右边
     *
     * @param leftNode
     * @param rightNode
     * @return
     */
    private static ListNode mergeSortList(ListNode leftNode, ListNode rightNode) {
        if (leftNode == null && rightNode == null) {
            return null;
        } else if (leftNode == null) {
            return rightNode;
        } else if (rightNode == null) {
            return leftNode;
        }
        ListNode tempNode = new ListNode();
        ListNode pNode = tempNode;
        while (leftNode != null && rightNode != null) {
            if (leftNode.data > rightNode.data) {
                pNode.next = rightNode;
                pNode = rightNode;
                rightNode = rightNode.next;
            } else {
                pNode.next = leftNode;
                pNode = leftNode;
                leftNode = leftNode.next;
            }
        }
        if (leftNode != null) {
            pNode.next = leftNode;
        }

        if (rightNode != null) {
            pNode.next = rightNode;
        }
        return tempNode.next;
    }

    /**
     * 通过快慢指针的方式找到中间节点
     *
     * @param node
     * @return
     */
    private static ListNode findMiddleNode(ListNode node) {
        ListNode slow = node;
        ListNode fast = node;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 將一個字符串轉換成單鏈表存儲的串
     *
     * @param data 字符串
     * @return
     */
    private static ListNode buildLink(int[] data) {
        int len = data.length;
        ListNode nextNode = new ListNode();
        nextNode.data = data[len - 1];
        nextNode.next = null;

        int index = len - 2;
        while (index >= 0) {
            ListNode node = new ListNode();
            node.data = data[index];
            node.next = nextNode;
            nextNode = node;
            index--;
        }
        return nextNode;
    }

    /**
     * 打印链表
     *
     * @param node
     */
    private static void printLink(ListNode node) {
        ListNode pNode = node;
        while (pNode != null) {
            System.out.print("" + pNode.data);
            pNode = pNode.next;
        }
        System.out.println();
    }

    public static class ListNode {
        public int data;
        public ListNode next;

    }


}
